#include <iostream>
#include <vector>
#include <stdexcept>

std::vector<std::vector<int>> g_vnResult; // 保存所有解
int BOARD_SIZE = 8;

// 判断是否需要收集解
bool NeedToCollect(int nId, const std::vector<int>& vnPath) {
    return nId == BOARD_SIZE;
}

// 收集解
void CollectResult(int nId, const std::vector<int>& vnPath) {
    g_vnResult.push_back(vnPath);
}

// 判断是否是死胡同
bool IsDeadNode(int nId, const std::vector<int>& vnPath) {
    return nId >= BOARD_SIZE;
}

// 判断是否可行
bool IsFeasible(int row, int col, const std::vector<int>& vnPath) {
    for (int i = 0; i < row; ++i) {
        if (vnPath[i] == col || abs(vnPath[i] - col) == row - i) {
            return false;
        }
    }
    return true;
}

// 获取下一个节点的ID
int GetNext(int nId) {
    return nId + 1;
}

// 回溯算法框架
void Backtrack(int nId, const std::vector<int>& vnRange, std::vector<int>& vnPath) {
    if (NeedToCollect(nId, vnPath)) {
        CollectResult(nId, vnPath);
    }
    
    if (IsDeadNode(nId, vnPath)) {
        return;
    }
    
    for (int val : vnRange) {
        if (!IsFeasible(nId, val, vnPath)) {
            continue;
        }
        
        vnPath.push_back(val); // 选择当前列
        Backtrack(GetNext(nId), vnRange, vnPath);
        vnPath.pop_back(); // 撤销选择
    }
}

// 打印解
void PrintResult(const std::vector<std::vector<int>>& results) {
    std::cout << "Total solutions: " << results.size() << std::endl;
    for (const auto& solution : results) {
        for (int col : solution) {
            std::cout << col << " ";
        }
        std::cout << std::endl;
    }
}

int main() {
    std::vector<int> vnRange(BOARD_SIZE);
    for (int i = 0; i < BOARD_SIZE; ++i) {
        vnRange[i] = i;
    }
    std::vector<int> vnPath;
    
    Backtrack(0, vnRange, vnPath);
    PrintResult(g_vnResult);
    
    return 0;
}